package leetCode;

import java.util.ArrayList;
import java.util.Stack;

/**
 * 要求常数时间返回最小的数
 * 但是栈顶元素不变
 * 可以用一个标记在push过程中标记这个最小的数字,那么在pop的过程中也要重新寻找最小数字
 * @author zhongfang
 *
 */
public class MinStack {
    ArrayList<Integer> theStack;
    int minPos;
    
    /** initialize your data structure here. */
    public MinStack() {
        theStack=new ArrayList<>();
        minPos=-1;
    }
    
    public void push(int x) {
        theStack.add(x);
        if(minPos==-1)
        	minPos=theStack.size()-1;
        else {
			if(x<theStack.get(minPos)){
				minPos=theStack.size()-1;
			}
		}
    }
    
    public void pop() {
        int n=theStack.size();
        theStack.remove(n-1);
        long minValue=(long)Integer.MAX_VALUE+1;
        if (theStack.isEmpty()) {
			minPos=-1;
		}else if(minPos==n-1){
        	for (int i=0;i<theStack.size();i++) {
        		Integer integer=theStack.get(i);
				if(integer<minValue){
					minValue=integer;
					minPos=i;
				}
			}
        }
    }
    
    public int top() {
        return theStack.get(theStack.size()-1);
    }
    
    public int getMin() {
        return theStack.get(minPos);
    }
    
    public static void main(String[] args) {
		MinStack stack=new MinStack();
		stack.push(2147483646);
		stack.push(2147483646);
		stack.push(2147483647);
		stack.top();
		stack.pop();
		stack.getMin();
		stack.pop();
		stack.getMin();
		stack.pop();
		stack.push(2147483647);
		stack.top();
		stack.getMin();
		stack.push(-2147483648);
		stack.top();
		stack.getMin();
		stack.pop();
		System.out.println(stack.theStack.size());
		stack.getMin();
	}
}


/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(x);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */
